package leetcode

// findOrder 检查是否可以完成所有课程的学习
// numCourses 表示课程总数
// prerequisites 是一个二维数组，其中每个元素表示一门课程的先决条件
// 返回一个包含所有课程的拓扑排序数组，如果无法完成所有课程，则返回空数组
func findOrder(numCourses int, prerequisites [][]int) []int {
	// 初始化结果数组
	ans := make([]int, 0)

	// 初始化课程的图表示和入度数组
	graph := make([][]int, numCourses)
	inGrades := make([]int, numCourses)

	// 遍历先决条件数组，构建课程的有向图和计算每个课程的入度
	for _, prerequisite := range prerequisites {
		begin, end := prerequisite[1], prerequisite[0]
		graph[begin] = append(graph[begin], end)
		inGrades[end]++
	}

	// 初始化入度为0的课程队列
	inZeroQueue := make([]int, 0)
	for i, inGrade := range inGrades {
		if inGrade == 0 {
			inZeroQueue = append(inZeroQueue, i)
		}
	}

	// 拓扑排序
	for len(inZeroQueue) > 0 {
		cur := inZeroQueue[0]
		inZeroQueue = inZeroQueue[1:]

		ans = append(ans, cur)

		// 遍历当前课程的所有后续课程，减少它们的入度
		for _, next := range graph[cur] {
			inGrades[next]--
			if inGrades[next] == 0 {
				inZeroQueue = append(inZeroQueue, next)
			}
		}
	}

	// 检查是否可以完成所有课程的学习
	// 为什么需要进行这个判断：
	// 例如，课程 0 的先决条件是课程 3，而课程 3 的先决条件又包括课程 0，形成了一个环路。
	// 因此，没有任何课程的入度为 0，就不会进行拓扑排序，最终 ans 为空数组 []int{}。这表明无法完成所有课程的学习
	// 若我们再在环外增加一个课程4指向环径中的课程0，只有课程4的入度为0，此时 ans 为 [4]，也无法完成所有课程的学习，此时也应该返回 []int{}
	if len(ans) < numCourses {
		return []int{}
	}

	return ans
}
